/*
 * BiTree.c
 *
 *  Created on: 2011-5-3
 *      Author: william nie
 */

#include"BiTree.h"
#include"BiTreeXmlHelper.h"
#include"Queue.h"

Status InitBiTree(BiTree **biTree) {

	printf("InitBiTree.\n");

	(*biTree) = (BiTree *) malloc(sizeof(BiTree));

	(*biTree)->root = NULL;

	(*biTree)->depth = 0;
	(*biTree)->nodnum = 0;
	(*biTree)->treesize = ((*biTree)->nodnum) * sizeof(BiTree);

	printf("InitBiTree Complete.\n\n");

	return OK;
}

Status DestroyNodes(BTNode *node){
	if(node==NULL){
		return OK;
	}

	if(node!=NULL){
		DestroyNodes(node->lchild);
		DestroyNodes(node->rchild);
	}

	free(node);

	return OK;
}

Status DestroyBiTree(BiTree *biTree) {
	DestroyNodes(biTree->root);
	free(biTree);
	return OK;
}

BiTree* CreateBiTree() {
	return LoadXmlBiTree();
}

Status ClearBiTree(BiTree *biTree) {
	DestroyNodes(biTree->root);
	biTree->root=NULL;
	biTree->depth=0;
	biTree->nodnum=0;
	biTree->treesize=0;
	return OK;
}

BOOL BiTreeEmpty(BiTree *biTree) {
	if (biTree->nodnum == 0) {
		return TRUE;
	}
	return FALSE;
}

int BiTreeDepth(BiTree *biTree) {
	return biTree->depth;
}

BTNode* Value(BTNode *btNode, int value) {
	static BOOL getOut = FALSE;
	BOOL findOrNot = FALSE;
	static BTNode *nodeToFind = NULL;

	if (getOut == TRUE) {
		return NULL;
	}

	if (btNode != NULL) {
		if (SearchBiVisit(btNode, value) == TRUE) {
			getOut = TRUE;
			findOrNot = TRUE;
		}
		Value(btNode->lchild, value);
		Value(btNode->rchild, value);
	}

	if (findOrNot == TRUE) {
		nodeToFind = btNode;
	}

	return nodeToFind;
}

Status Assign(BiTree *biTree, int oldValue, int newValue) {
	BTNode *node = Value(biTree->root, oldValue);
	node->data = newValue;
	return OK;
}

BTNode* FindParent(BTNode *btNode, BTNode* child) {
	static BOOL getOut = FALSE;
	BOOL findOrNot = FALSE;
	static BTNode *parent = NULL;

	if (getOut == TRUE) {
		return NULL;
	}

	if (btNode != NULL) {
		if (btNode->lchild == child || btNode->rchild == child) {
			getOut = TRUE;
			findOrNot = TRUE;
		}
		FindParent(btNode->lchild, child);
		FindParent(btNode->rchild, child);
	}

	if (findOrNot == TRUE) {
		parent = btNode;
	}

	return parent;
}

BTNode* Parent(BiTree *biTree, BTNode *elem) {
	return FindParent(biTree->root, elem);
}

BTNode* LeftChild(BTNode *elem) {
	return elem->lchild;
}

BTNode* RightChild(BTNode *elem) {
	return elem->rchild;
}

BTNode* LeftSibling(BiTree *biTree, BTNode *elem) {
	BTNode *parent = Parent(biTree, elem);
	if (parent->lchild == elem) {
		return NULL;
	} else {
		return parent->lchild;
	}

}

BTNode* RightSibling(BiTree *biTree, BTNode *elem) {
	BTNode *parent = Parent(biTree, elem);
	if (parent->rchild == elem) {
		return NULL;
	} else {
		return parent->rchild;
	}
}


Status DeleteChild(BiTree *biTree, int parentData, LR pos) {
	BTNode *parent = Value(biTree->root, parentData);
	if(pos==LEFT){
		parent->lchild = NULL;
	} else if(pos==RIGHT) {
		parent->rchild = NULL;
	}

	return OK;
}

Status PreOrderTraverse(BTNode *btNode, Visit visit) {
	static BOOL getOut = FALSE;

	if (getOut == TRUE) {
		return OK;
	}

	if (btNode != NULL) {
		if (visit(btNode) == FALSE) {
			getOut = TRUE;
		}
		PreOrderTraverse(btNode->lchild, visit);
		PreOrderTraverse(btNode->rchild, visit);
	}

	return OK;

}

Status InOrderTraverse(BTNode *btNode, Visit visit) {
	static BOOL getOut = FALSE;

	if (getOut == TRUE) {
		return OK;
	}

	if (btNode != NULL) {
		InOrderTraverse(btNode->lchild, visit);
		if (visit(btNode) == FALSE) {
			getOut = TRUE;
		}
		InOrderTraverse(btNode->rchild, visit);
	}

	return OK;

}

Status PostOrderTraverse(BTNode *btNode, Visit visit) {
	static BOOL getOut = FALSE;

	if (getOut == TRUE) {
		return OK;
	}

	if (btNode != NULL) {
		PostOrderTraverse(btNode->lchild, visit);
		PostOrderTraverse(btNode->rchild, visit);
		if (visit(btNode) == FALSE) {
			getOut = TRUE;
		}
	}

	return OK;
}

Status LevelOrderTraverse(BiTree *biTree, Visit visit) {
	BiQueue *queue;
	InitBiQueue(&queue);
	BTNode *node = biTree->root;
	visit(node);
	if (node->lchild) {
		EnBiQueue(queue, node->lchild);
	}
	if (node->rchild) {
		EnBiQueue(queue, node->rchild);
	}

	while (!BiQueueEmpty(queue)) {
		node = DeBiQueue(queue);
		visit(node);

		if (node->lchild) {
			EnBiQueue(queue, node->lchild);
		}
		if (node->rchild) {
			EnBiQueue(queue, node->rchild);
		}
	}

	DestroyBiQueue(&queue);
	fflush(stdin);
	getchar();
	exit(1);
	return OK;
}

BOOL DefaultBiVisit(BTNode *elem) {
	printf("%d ", elem->data);
	return TRUE;
}

BOOL SearchBiVisit(BTNode *elem, int data) {
	if (elem->data == data) {
		return TRUE;
	}
	return FALSE;
}

Status InitBiQueue(BiQueue **queue) {
	(*queue)->front = (*queue)->rear = (BQNode*) malloc(sizeof(BQNode));
	if ((*queue)->front == NULL) {
		fprintf(stderr, "ERROR WHEN CREATE QUEUE!");
		fflush(stdin);
		getchar();
		exit(OVERFLOW);
	}
	(*queue)->front->next = NULL;
	return OK;
}

Status DestroyBiQueue(BiQueue **queue){

	while((*queue)->front != NULL){
		(*queue)->rear = (*queue)->front->next;
		free((*queue)->front);
		(*queue)->front = (*queue)->rear;
	}
//	*queue = NULL;
	return OK;
}

BOOL BiQueueEmpty(BiQueue *queue){
	if(queue->front == queue->rear){
		return TRUE;
	}
	return FALSE;
}

Status EnBiQueue(BiQueue *queue, BQElemType *node) {
	BQNode *newNode = (BQNode*) malloc(sizeof(BQNode));

	if (newNode == NULL) {
		fprintf(stderr, "ERROR WHEN CREATE NEW NODE!");
		fflush(stdin);
		getchar();
		exit(OVERFLOW);
	}

	newNode->data = node;
	newNode->next = NULL;

	queue->rear->next = newNode;
	queue->rear = newNode;

	return OK;
}

BQElemType* DeBiQueue(BiQueue *queue) {

	if(queue->front == queue->rear){
		return NULL;
	}

	BQNode *node = queue->front->next;
	queue->front->next = node->next;
	if(node == queue->rear){
		queue->rear = queue->front;
	}

	BQElemType *elem = node->data;
	free(node);

	return elem;
}
